Computer networks have evolved to provide sophisticated functionality in a large variety of contexts. Providing such functionality, however, often involves complex systems that malicious entities may try to exploit. One such attack involves denial-of-service attacks, which can be disruptive to computer systems on a network. In a distributed denial-of-service attack, for instance, large numbers of requests are sent to a computer system to attempt to overload the computer system. One way to mitigate against such attacks is to configure a service such that requests to the service incur some sort of expense, thereby providing a disincentive to participating in the attack. One such expense involves imposing a condition that a client submitting a request expend more computational resources (e.g., CPU cycles) to cause the request to be fulfilled. Other contexts also involve issues that are addressable, at least in part, through imposition of an expense in exchange for a service's operation.
However, imposing such expenses in exchange for computer system functionality is often probabilistic in nature, meaning that the expense may vary, often significantly. In other words, making a request may sometimes incur a higher computational expense and sometimes incur a lower computational expense. The variance in expenses may detrimentally impact requestor systems that provide assurances of performance (e.g., a quality-of-service assurances) which are based at least in part on accessing computational resources of a service that imposes such expenses in exchange for access to the computational resources.